Palindrome Linked List

LeetCode 234 | Difficulty: Easy

Easy

Problem Description

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

- The number of nodes in the list is in the range `[1, 10^5]`.

- `0 <= Node.val <= 9`

Follow up: Could you do it in O(n) time and O(1) space?

Topics: Linked List, Two Pointers, Stack, Recursion

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 176 ms)

Metric	Value
Runtime	176 ms
Memory	N/A
Date	2017-09-22

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        if(head==null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = Reverse(slow.next);
        slow = slow.next;
        while (slow != null)
        {
            if(head.val != slow.val) return false;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    private static ListNode Reverse(ListNode head)
    {
        ListNode rev = null;
        while (head != null)
        {
            ListNode temp = head;
            head = head.next;
            temp.next = rev;
            rev = temp;
        }
        return rev;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-02) — 459 ms, 52 MB

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        if(head==null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = Reverse(slow);
        while (slow != null)
        {
            if(head.val != slow.val) return false;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    private static ListNode Reverse(ListNode head)
    {
        ListNode rev = null;
        while (head != null)
        {
            ListNode temp = head;
            head = head.next;
            temp.next = rev;
            rev = temp;
        }
        return rev;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Stack	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?